package uestc.lj.basic.graph;

import java.util.*;

/**
 * 拓扑排序
 *
 * @Author:Crazlee
 * @Date:2021/11/24
 */
public class Code03_TopoSort {
	/**
	 * 实现拓扑排序算法
	 *
	 * @param graph 图
	 * @return 拓扑排序节点顺序
	 */
	public static List<Node> topologySort(Graph graph) {
		//key——某一个node，value——剩余的入度
		HashMap<Node, Integer> inMap = new HashMap<>();
		//入度为0的点才能入队
		Queue<Node> zeroInQueue = new LinkedList<>();

		for (Node node : graph.nodes.values()) {
			inMap.put(node, node.in);
			if (node.in == 0) {
				zeroInQueue.add(node);
			}
		}
		//拓扑排序
		List<Node> result = new ArrayList<>();
		while (!zeroInQueue.isEmpty()) {
			Node cur = zeroInQueue.poll();
			result.add(cur);
			// 删除当前点及其所影响的点
			for (Node next : cur.nexts) {
				inMap.put(next, inMap.get(next) - 1);
				if (inMap.get(next) == 0) {
					zeroInQueue.add(next);
				}
			}
		}
		return result;
	}
}
